#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/9/4 9:08
# ===========================================
#       题目名称： 52. N 皇后 II
#       题目地址： https://leetcode.cn/problems/n-queens-ii/description/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================


class Solution:
    def totalNQueens(self, n: int) -> int:
        dp = [["."] * n for _ in range(n)]  # 单个皇后
        dps = []  # 皇后群
        i = 0
        while i < n:
            if i == 0:
                for j in range(n):
                    cur_dp = [item.copy() for item in dp].copy()
                    cur_dp[i][j] = "Q"
                    dps.append(cur_dp)
            else:
                temp_dps = []
                for dp in dps:
                    for j in range(n):
                        is_ok = True
                        # 验证x  因为通过循环不断的开启新的皇后棋盘 所以轴无需判断
                        # 验证y
                        x, y = i, j
                        while is_ok and x > -1:
                            if dp[x][y] == "Q":
                                is_ok = False
                                break
                            x -= 1
                        if not is_ok:
                            continue
                        # 验证斜线
                        # 左上角
                        x, y = i - 1, j - 1
                        while is_ok and x > -1 and y > -1:
                            if dp[x][y] == "Q":
                                is_ok = False
                                break
                            x -= 1
                            y -= 1
                        # 右上角
                        x, y = i - 1, j + 1
                        while is_ok and x > -1 and y < n:
                            if dp[x][y] == "Q":
                                is_ok = False
                                break
                            x -= 1
                            y += 1
                            # 左下角
                        x, y = i + 1, j - 1
                        while is_ok and x < n and y > -1:
                            if dp[x][y] == "Q":
                                is_ok = False
                                break
                            x += 1
                            y -= 1
                        # 右下角
                        x, y = i + 1, j + 1
                        while is_ok and x < n and y < n:
                            if dp[x][y] == "Q":
                                is_ok = False
                                break
                            x += 1
                            y += 1
                        if is_ok:
                            # 将符合规范的数据存入临时列表
                            cur_dp = [item.copy() for item in dp].copy()
                            cur_dp[i][j] = "Q"
                            temp_dps.append(cur_dp)
                dps = temp_dps
            i += 1
        return len(dps)


if __name__ == '__main__':
    s = Solution()
    # 2
    print(s.totalNQueens(n=4))
    # 1
    print(s.totalNQueens(n=1))
